/*
 * gcc -std=c++0x stdmap.cpp -o stdmap
 */
#include <iostream>
#include <string>
#include <map>
#include <unordered_map>
using namespace std;

typedef struct _value_t {
    int v;
    string sv;
    _value_t() : v(0), sv() { } /* required for maps */
    _value_t(int v, const char *sv) {
        this->v = v;
        this->sv = sv;
    }
} value_t;

void test_map()
{
    cout << "--- test std::map ---" << endl;
    map<string, value_t> m;
    m["111"] = value_t(111, "111s");
    m["222"] = value_t(222, "222s");
    m["333"] = value_t(333, "333s");
    m["333"] = value_t(333, "333s");
    m["222"] = value_t(444, "444s");
    for (map<string, value_t>::const_iterator it = m.begin(); it != m.end(); ++it) {
        cout << "key=" << it->first << ", value=[" << it->second.v << "," << it->second.sv << "]." << endl;
    }
}

void test_multimap()
{
    cout << "--- test std::multimap ---" << endl;
    multimap<string, value_t> m;
    m.insert(pair<string, value_t>("111", value_t(111, "111s")));
    m.insert(pair<string, value_t>("222", value_t(222, "222s")));
    m.insert(pair<string, value_t>("333", value_t(333, "333s")));
    m.insert(pair<string, value_t>("333", value_t(333, "333s")));
    m.insert(pair<string, value_t>("222", value_t(444, "444s")));
    for (multimap<string, value_t>::const_iterator it = m.begin(); it != m.end(); ++it) {
        cout << "key=" << it->first << ":" << endl;
        multimap<string, value_t>::const_iterator it2 = m.upper_bound(it->first);
        for ( ; it != it2; ++it) {
            cout << "    value=[" << it->second.v << "," << it->second.sv << "]" << endl;
        }
        --it;
    }
}

/* hash */
void test_unordered_map()
{
    cout << "--- test std::unordered_map ---" << endl;
    unordered_map<string, value_t> m;
    m["111"] = value_t(111, "111s");
    m["222"] = value_t(222, "222s");
    m["333"] = value_t(333, "333s");
    m["333"] = value_t(333, "333s");
    m["222"] = value_t(444, "444s");
    int count = m.bucket_count();
    for (int i = 0; i < count; ++i) {
        cout << "bucket=#" << i << ":" << endl;
        for (auto it = m.cbegin(i); it != m.cend(i); ++it) {
            cout << "    key=" << it->first << ", value=[" << it->second.v << "," << it->second.sv << "]." << endl;
        }
    }
}

/* hash */
void test_unordered_multimap()
{
    cout << "--- test std::unordered_multimap ---" << endl;
    unordered_multimap<string, value_t> m;
    m.insert(pair<string, value_t>("111", value_t(111, "111s")));
    m.insert(pair<string, value_t>("222", value_t(222, "222s")));
    m.insert(pair<string, value_t>("333", value_t(333, "333s")));
    m.insert(pair<string, value_t>("333", value_t(333, "333s")));
    m.insert(pair<string, value_t>("222", value_t(444, "444s")));
    int count = m.bucket_count();
    for (int i = 0; i < count; ++i) {
        cout << "bucket=#" << i << ":" << endl;
        for (auto it = m.cbegin(i); it != m.cend(i); ++it) {
            cout << "    key=" << it->first << ",value=[" << it->second.v << "," << it->second.sv << "]." << endl;
        }
    }
}

int main()
{
    /*
     * - http://www.cplusplus.com/reference/map/map/
     * - Maps are associative containers that store elements formed by a
     * combination of a key value and a mapped value, following a specific
     * order.
     * - Maps are typically implemented as binary search trees.
     */
    test_map();
    /*
     * - http://www.cplusplus.com/reference/map/multimap/
     * - Multimaps are associative containers that store elements formed by a
     * combination of a key value and a mapped value, following a specific
     * order, and where multiple elements can have equivalent keys.
     * - Multimaps are typically implemented as binary search trees.
     */
    test_multimap();
    /*
     * - http://www.cplusplus.com/reference/unordered_map/unordered_map/
     * - Maps are associative containers that store elements formed by a
     * combination of a key value and a mapped value, following a specific
     * order.
     * - Internally, the elements in the unordered_map are not sorted in any
     * particular order with respect to either their key or mapped values, but
     * organized into buckets depending on their hash values to allow for fast
     * access to individual elements directly by their key values (with a
     * constant average time complexity on average).
     */
    test_unordered_map();
    /*
     * - http://www.cplusplus.com/reference/unordered_map/unordered_multimap/
     * - Unordered multimaps are associative containers that store elements
     * formed by the combination of a key value and a mapped value, much like
     * unordered_map containers, but allowing different elements to have
     * equivalent keys.
     * - Internally, the elements in the unordered_multimap are not sorted in
     * any particular order with respect to either their key or mapped values,
     * but organized into buckets depending on their hash values to allow for
     * fast access to individual elements directly by their key values (with a
     * constant average time complexity on average).
     */
    test_unordered_multimap();

    return 0;
}
